/**
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/** 
 * Solution 1:双指针
 *  定义两个指针，pre在前cur在后，每次都让两个指针进行一次局部反转
 *  局部反转后两个指针都往前移一个位置，循环完成直至链表尾部
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = nullptr, *pre = head;

        while(pre != nullptr){
            // 暂存节点
            ListNode* temp = pre->next;
            // 反转节点
            pre->next = cur;
            // 两个指针向前移动一位
            cur = pre;
            pre = temp;
        }
        // cur循环到链表最后节点时，在它前面的pre已经是空节点，cur成为新的头节点
        return cur;

    }
};

/**
 * Solution 2:递归
 * 这次的递归比较难理解，可以看leetcode收藏的题解动画
 * 
 * 1.递归函数的参数和返回值都是头指针
 * 2.终止条件是当前节点或者下一节点==NULL
 * 3.单层递归逻辑是在函数内部改变节点的指向
 */
class Solution_2 {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        
        // 先从链表头递归遍历到链表尾
        // 到尾部后，在上一步指令return链表尾的节点，对其和其前一个节点进行反转
        // 处理完当前节点后返回前一个节点，然后循环这两部操作，直到把所有节点都反转完
        ListNode* cur = reverseList(head->next);
        // 以1，2节点类比，就是把1->next->next(即2->next)指向1，把1指向2的指针删掉
        head->next->next = head;
        head->next = nullptr;
        return cur;
        

    }
};